/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月03日
*   描    述：
*
================================================================*/

/*
 * 给你一个整数数组 nums
 * ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 * 示例 1：
 *   输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 *   输出：6
 *   解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 * 示例 2：
 *   输入：nums = [1]
 *   输出：1
 *
 * 示例 3：
 *   输入：nums = [5,4,-1,7,8]
 *   输出：23
 *
 * 提示：
 *   1 <= nums.length <= 105
 *   -104 <= nums[i] <= 104
 *
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 */

#include <stdio.h>

int maxSubArray(int* nums, int numsSize) {
  int current_sum = nums[0];
  int max_sum = nums[0];

  for (int i = 1; i < numsSize; i++) {
    current_sum = (nums[i] > current_sum + nums[i]) ? nums[i] : current_sum + nums[i];
    max_sum = (max_sum > current_sum) ? max_sum : current_sum;
  }

  return max_sum;
}

int main() {
  int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  int numsSize = sizeof(nums) / sizeof(nums[0]);

  int result = maxSubArray(nums, numsSize);
  printf("Maximum sum of a subarray: %d\n", result);

  return 0;
}
